package primary.primary0;

/**
 *
 */
public class S0064最小路径和 {


    /**
     * 93，一维递推
     */
    class Solution {
        public int minPathSum(int[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0){
                return -1;
            }
            int[] record = new int[grid[0].length];
            for(int i = 0; i < grid.length; i++){
                for(int j = 0; j < grid[0].length; j++){
                    //System.out.println(Arrays.toString(record));
                    if(i == 0){
                        if(j == 0){
                            record[j] = grid[0][0];
                        }else{
                            record[j] = record[j - 1] + grid[i][j];
                        }
                    }else{
                        if(j == 0){
                            record[j] = record[j] + grid[i][j];
                        }else{
                            record[j] = Math.min(record[j], record[j - 1]) + grid[i][j];
                        }
                    }
                }
            }
            return record[grid[0].length - 1];
        }
    }


    /**
     * 就一行record, 正常套路, 但是这个边界条件肯定有更好的处理方法。
     * todo: 边界条件处理
     */
    public int minPathSum(int[][] grid) {
        int rowSize = grid.length;
        int colSize = grid[0].length;
        int[] record = new int[colSize];
        for(int i = 0; i < rowSize; i++){
            if(i == 0){
                for(int j = 0; j < colSize; j++){
                    if(j == 0){
                        record[j] = grid[i][j];
                    }else{
                        record[j] = record[j - 1] + grid[i][j];
                    }
                }
            }else{
                for(int j = 0; j < colSize; j++){
                    if(j == 0){
                        // 下移一步
                        record[j] += grid[i][j];
                    }else{
                        // 右移一步
                        record[j] = Math.min(record[j], record[j - 1]) + grid[i][j];
                    }
                }
            }

            //System.out.println(Arrays.toString(record));
        }

        return record[colSize - 1];
    }
}
